1. Technical Field
This invention relates generally to providing directory services in a distributed computing environment.
2. Description of the Related Art
A directory service is the central point where network services, security services and applications can form an integrated distributed computing environment. Typical uses of a directory services may be classified into several categories. A “naming service” (e.g., DNS and DCE Cell Directory Service (CDS)) uses the directory as a source to locate an Internet host address or the location of a given server. A “user registry” (e.g., Novell NDS) stores information about users in a system composed of a number of interconnected machines. The central repository of user information enables a system administrator to administer the distributed system as a single system image. Still another directory service is a “white pages” lookup provided by some e-mail clients, e.g., Netscape Communicator, Lotus Notes, Endora and the like).
With more and more applications and system services demanding a central information repository, the next generation directory service will need to provide system administrators with a data repository that can significantly ease administrative burdens. In addition, the future directory service must also provide end users with a rich information data warehouse that allows them to access department or company employee data, as well as resource information, such as name and location of printers, copy machines, and other environment resources. In the Internet/intranet environment, it will be required to provide user access to such information in a secure manner.
To this end, the Lightweight Directory Access Protocol (LDAP) has emerged as an IETF open standard to provide directory services to applications ranging from e-mail systems to distributed system management tools. LDAP is an evolving protocol that is based on a client-server model in which a client makes a TCP/IP connection to an LDAP server, sends requests, and receives responses. The LDAP information model in particular is based on an “entry,” which contains information about some object. Entries are typically organized in a specified tree structure, and each entry is composed of attributes.
LDAP provides a number of known functions including query (search and compare), update, authentication and others. The search and compare operations are used to retrieve information from the database. For the search function, the criteria of the search is specified in a search filter. The search filter typically is a Boolean expression that consists of qualifiers including attribute name, attribute value and Boolean operators like AND, OR and NOT. Users can use the filter to perform complex search operations. One filter syntax is defined in RFC 2254.
LDAP thus provides the capability for directory information to be efficiently queried or updated. It offers a rich set of searching capabilities with which users can put together complex queries to get desired information from a backing store. Increasingly, it has become desirable to use a relational database for storing LDAP directory data. Representative database implementations include DB/2, Oracle, Sybase, Informix and the like. As is well known, Structured Query Language (SQL) is the standard language used to access such databases.
Relational database guidelines (e.g., the First Normal Form) requires that attributes within each tuple are ordered and complete and that searchable domains permit only simple values. Further, simple values cannot be decomposed into multiple values, and they cannot be decomposed into multiple relations. If these guidelines are not followed, the database application becomes quite difficult to manage. Such limitations present difficulties when it is desired to use a relational database as an LDAP backing store. In particular, LDAP allows multi-value attributes. As a result, implementation of the LDAP directory model requires that there is a relation (or table) for each searchable attribute. This “per attribute” table design basically normalizes all the attributes to achieve a manageable implementation. A schema of this type provides a general solution for LDAP applications.
However, for applications which rarely use multi-value attributes, the per attribute table does not perform well for certain functions. In particular, add/updates are very expensive. Thus, for example, for an entry with ten attributes, more than ten tables need to be updated. As another example, logical operations involving multiple attributes require expensive table joins to perform the operation.
It would be highly desirable to provide a database schema to solve the performance problem of per-attribute tables, especially for directory applications that rarely use multi-value attributes. The present invention solves this problem.